package leetcode.editor.cn.dsa23_graph;
//节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
//
// 示例1: 
//  输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
// 输出：true
//
// 示例2: 
//  输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [
//1, 3], [2, 3], [3, 4]], start = 0, target = 4
// 输出 true
//
// 提示： 
// 节点数量n在[0, 1e5]范围内。
// 节点编号大于等于 0 小于 n。 
// 图中可能存在自环和平行边。 
// 
// Related Topics 图 
// 👍 20 👎 0

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class RouteBetweenNodesLcci0401_1 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private ArrayList<ArrayList<Integer>> adj;
        public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
            // 建立邻接表列表
            adj = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                adj.add(new ArrayList<>());
            }
            for (int i = 0; i < graph.length; i++) {
                // 节点数据值作为邻接表列表索引
                adj.get(graph[i][0]).add(graph[i][1]);
            }
            // 数组表示节点是否已被访问过
            boolean[] visited = new boolean[n];
            visited[start] = true;
            // 开始递归
            return findWhetherExistsPath_recursive(start, target, visited);
        }
        private boolean findWhetherExistsPath_recursive(int start, int target, boolean[] visited) {
            if (start == target) return true;
            // 遍历start出发所有边，进行DFS
            ArrayList<Integer> adjacency = adj.get(start);
            for (Integer vext : adjacency) {
                if (!visited[vext]) {
                    visited[vext] = true;
                    // 任意一条路径返回true，则查询终止
                    boolean result = findWhetherExistsPath_recursive(vext, target, visited);
                    if (result) return true;
                }
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}